package 并查集;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 岛屿数量.java
 * @Description TODO
 * @createTime 2020年11月21日 15:50:00
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 *
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 *
 * 此外，你可以假设该网格的四条边均被水包围。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：grid = [
 *   ["1","1","1","1","0"],
 *   ["1","1","0","1","0"],
 *   ["1","1","0","0","0"],
 *   ["0","0","0","0","0"]
 * ]
 * 输出：1
 * 示例 2：
 *
 * 输入：grid = [
 *   ["1","1","0","0","0"],
 *   ["1","1","0","0","0"],
 *   ["0","0","1","0","0"],
 *   ["0","0","0","1","1"]
 * ]
 * 输出：3
 *
 * 并查集中维护连通分量的个数，在遍历的过程中：
 *
 * 相邻的陆地（只需要向右看和向下看）合并，只要发生过合并，岛屿的数量就减少 11；
 * 在遍历的过程中，同时记录空地的数量；
 * 并查集中连通分量的个数 - 空地的个数，就是岛屿数量。
 *
 *
 */
public class 岛屿数量 {
    public class Solution {

        private int rows;
        private int cols;

        public int numIslands(char[][] grid) {
            rows = grid.length;
            if (rows == 0) {
                return 0;
            }
            cols = grid[0].length;

            // 空地的数量
            int spaces = 0;
            UnionFind unionFind = new UnionFind(rows * cols);
            int[][] directions = {{1, 0}, {0, 1}};
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (grid[i][j] == '0') {
                        spaces++;
                    } else {
                        // 此时 grid[i][j] == '1'
                        for (int[] direction : directions) {
                            int newX = i + direction[0];
                            int newY = j + direction[1];
                            // 先判断坐标合法，再检查右边一格和下边一格是否是陆地
                            if (newX < rows && newY < cols && grid[newX][newY] == '1') {
                                unionFind.union(getIndex(i, j), getIndex(newX, newY));
                            }
                        }
                    }
                }
            }
            return unionFind.getCount() - spaces;
        }

        private int getIndex(int i, int j) {
            return i * cols + j;
        }

        private class UnionFind {
            /**
             * 连通分量的个数
             */
            private int count;
            private int[] parent;

            public int getCount() {
                return count;
            }

            public UnionFind(int n) {
                this.count = n;
                parent = new int[n];
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                }
            }

            private int find(int x) {
                while (x != parent[x]) {
                    parent[x] = parent[parent[x]];
                    x = parent[x];
                }
                return x;
            }

            public void union(int x, int y) {
                int xRoot = find(x);
                int yRoot = find(y);
                if (xRoot == yRoot) {
                    return;
                }

                parent[xRoot] = yRoot;
                count--;
            }
        }
    }

}
